/*
 * Copyright (c) 2008, Justin Choy
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1) Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer.
 * 
 * 2) Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution.
 * 
 * 3) Neither the name of the owner nor the names of its contributors may 
 * be used to endorse or promote products derived from this software without 
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */
package algorithms;

import data.Array;
import error.OutOfMemoryException;
import error.ProgrammingErrorException;

/**
 * An example of using the Shell sort Algorithm
 * The Shell sort first sorts small sub-arrays until it sorts the entire array.
 * The sub-srrays are determined by defined as the all elements that are h
 * indexes apart. after all the first sub-arrays are sorted, we decrement h and
 * sort these new bigger sub arrays until we eventually get to h = 1. The
 * Interval ( or h ) is calculated by an algorithm.
 * 
 * O(N^(3/2)) - O(N^(7/8))
 * 
 * @author jchoy
 */
public class ShellSort {
    public ShellSort() {
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        try {
            ShellSort.ShellSortedArray array 
                = new ShellSort().new ShellSortedArray();
            
            System.out.println( "Filling Array...");
            array.fillWithRandomNumbers(50000);
            
            System.out.println( "Shell Sorting..." );
            
            long startTime = System.currentTimeMillis();
            array.sort();
            long stopTime = System.currentTimeMillis();
            long sortTime = stopTime - startTime;
            
            System.out.println( "It took " + Long.toString(sortTime) + "ms");
            
            System.out.print( "Testing sort...");
            
            if ( array.isOrdered() == true) {
                System.out.println( "PASS!" );
            } else {
                System.out.println( "FAIL!" );
            }
            
        } catch (ProgrammingErrorException e) {
            System.out.println( e.getMessage() );
        } catch (OutOfMemoryException e) {
            System.out.println(e.getMessage());
        }
    }
    
    
    class ShellSortedArray extends Array {
        public ShellSortedArray() {
        }
        
        /**
         * Calculates the interval used in the shell sort algorithm using
         * Knuth's famous recursive equation ( h = 3 * h + 1 )
         * 
         * @return The largest interval appropriate for the number of elements
         * in the array
         */
        private int calculateLargestInterval() {
            long interval = 1;
            
            /* Use Knuth's formula to get interval 1 iteration over
             * numElements. Since this will actuall get bigger than numElements,
             * we have to use a long
             */
            while ( interval <= (long) getNumElements() ) {
                interval = 3 * interval + 1;
            }
            
            /* Go back one iteration so the interval is less than numElements*/
            interval = (interval - 1) / 3;
            
            return (int) interval;           
        }
        
        /**
         * Decrements the interval used in the shell sort algorith using
         * the inverse of Knuth's famous recursive equation
         * 
         * @param interval The current interval
         * @return The interval right before this one
         */
        private int decrementInterval( int interval ) {
            return ( (interval - 1) / 3 );
        }
        
        /**
         * Sorts the array using shell sort.
         * 
         * @throws ProgrammingErrorException 
         */
        public void sort() throws ProgrammingErrorException {
            int interval = calculateLargestInterval();
            int subArrayIndex = 0;
            int innerIndex = 0;
            long temp = 0;
            
            /* Keep looping till out interval is 1 */
            while ( interval > 0 ) {
                
                /* For loop for shifting out starting point 1 to the right */
                for ( subArrayIndex = interval; 
                                               subArrayIndex < getNumElements();
                                               subArrayIndex++ ) {
                    
                    /* Now we basically have a sub-array that we need to sort.
                     * The sub-array (from the right) start at subArrayIndex,
                     * and consists of every element with a positive index
                     * given by the equation subArrayIndex - n *interval.
                     * So if subArrayIndex = 18 and interval = 4 our sub-array
                     * consists of elements 18, 14, 10, 6, 2. Because we started
                     * at small subArrayIndexes, the smaller sub-array
                     * of 14, 10, 6, 2 should already be sorted therefore we
                     * just need to insert the 18th element in the correct
                     * position. (Use insertion sort)
                     */
                    
                    /* Store the element in question */
                    temp = array[subArrayIndex];
                    innerIndex = subArrayIndex;
                    
                    /* Keep looping through the smaller sub-array and shift
                     * all values that are bigger than element in question
                     * until we find the correct spot and insert it into that
                     * spot. Note we are comparing (innerIndex - interval)
                     */
                    while ( (innerIndex > (interval - 1)) &&
                            array[innerIndex - interval] > temp ) {
                        
                        array[innerIndex] = array[innerIndex - interval];
                        innerIndex -= interval;
                    }
                    
                    array[innerIndex] = temp;
                    
                } /* end For ( all elements) */
                
                /* Here we are done with our for loop meaning we have just
                 * interval sorted our array. decrement interval and go again
                 */
                interval = decrementInterval(interval);
                
            } /* end while ( interval > 0 ) */
        }
    }
    
}
